## An illustration of the McEliece system, step by step

from PyM import *


# 0. Construct the binary field, and call it K
K = Zn(2,'K')

# 1. Construct F32 with generator named 'a'
[F,a] = extension(K,get_irreducible_polynomial(K,5),'a','F')

# 2. Get a random monic irreductible polynomial p in F[T] 
#    of degree 3
p = get_irreducible_polynomial(F,3,'T')
show('p :',p) 


# 3. Create the Goppa code C using p**2 over
#    the non-zero elements of F (expression X[1:]).
#    It corrects deg(p) = 3 errors
X = Set(F)
C = Goppa(p,X) #,X[1:]

# 4. Control matrix of C over F 
HH = H_(C)
show(shape(HH))

#    and over K
H1 = blow(HH,K)
show(shape(H1))
show(rank(H1))


# 5. Generating matrix over K, G. We see that k = 16
G = transpose(kernel(H1))
show(shape(G))

# 6. Matrix S of the private key; K_(G) is K, 
#    as C is defined over K.
#    S is an invertible binary matrix of order 16.

S=rd_GL(nrows(G),K_(G))
show(det(S))

# 7. Matrix P (with integer entries) of the private key. 
#    det(P) can be 1 or -1

P = rd_permutation_matrix(ncols(G))
show(det(P))

# 8. Public key (G1,t)

G1 = S*G*P
show(shape(G1))

t = nrows(H_(C))//2
show('t :',t)

# 9. Encryption of a random information vector u

# random information vector
u = rd_vector(K,nrows(G1))
show('u :',u)

# coding with G1
x = u*G1 
show('x :',x)

# random vector of weight t = 3 of same length as x
e = rd_error_vector(len(x),t, K) 
show('e :',e)

# vector transmitted to receiver
x1 = x+e 
show('x1 :',x1)


# 10. Decrypting. The inverse of P it its transpose

y = x1*transpose(P) 
show('y :',y)

# decrypting, with PGZ in this occasion
x2 = PGZm(y,C) 
show('x2 :',x2)

# get uG by linear algebra
u1 = solve_linear_system(transpose(G),transpose(x2))
u1 = transpose(u1)
show('u1 :',u1)

# undo the scrabbling by S
uu=u1/S
show('uu :',uu)

# check that it coincides with the origial message
show('uu = u ?')
show(uu == u)